Auflistung nach Schlagwort "Temporal logic"

Sortiert nach: Sortierung: Ergebnisse:

  • Affine Encodings for Optimal Monitoring of Temporal Properties under Uncertain Observation 
    Fränzle, Martin (Hannover : Gottfried Wilhelm Leibniz Universität, 2022)
    [no abstract available]
  • Backdoors for linear temporal logic 
    Meier, Arne; Ordyniak, Sebastian; Sridharan, Ramanujan; Schindler, Irena (Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2017)
    In the present paper, we introduce the backdoor set approach into the field of temporal logic for the global fragment of linear temporal logic. We study the parameterized complexity of the satisfiability problem parameterized ...
  • The complexity of generalized satisfiability for linear temporal logic 
    Bauland, Michael; Schneider, Thomas; Schnoor, Henning; Schnoor, Ilka; Vollmer, Heribert (Braunschweig : International Federation for Computational Logic, 2009)
    In a seminal paper from 1985, Sistla and Clarke showed that satisfiability for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of temporal operators used. If, in contrast, the set ...
  • The Complexity of Satisfiability for Fragments of CTL and CTL⋆ 
    Meier, Arne; Mundhenk, Martin; Thomas, Michael; Vollmer, Heribert (Amsterdam : Elsevier BV, 2008)
    The satisfiability problems for CTL and CTL⋆ are known to be EXPTIME-complete, resp. 2EXPTIME-complete (Fischer and Ladner (1979), Vardi and Stockmeyer (1985)). For fragments that use less temporal or propositional operators, ...
  • Model checking CTL is almost always inherently sequential 
    Beyersdorff, Olaf; Meier, Arne; Mundhenk, Martin; Schneider, Thomas; Thomas, Michael; Vollmer, Heribert (Braunschweig : International Federation for Computational Logic, 2011)
    The model checking problem for CTL is known to be P-complete (Clarke, Emerson, and Sistla (1986), see Schnoebelen (2002)). We consider fragments of CTL obtained by restricting the use of temporal modalities or the use of ...
  • Parametrised complexity of satisfiability in temporal logic 
    Lück, Martin; Meier, Arne; Schindler, Irena (Association for Computing Machinery, 2017)
    We apply the concept of formula treewidth and pathwidth to computation tree logic, linear temporal logic, and the full branching time logic. Several representations of formulas as graphlike structures are discussed, and ...
  • Team semantics for the specification and verification of hyperproperties 
    Krebs, Andreas; Meier, Arne; Virtema, Jonni; Zimmermann, Martin (Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2018)
    We develop team semantics for Linear Temporal Logic (LTL) to express hyperproperties, which have recently been identified as a key concept in the verification of information flow properties. Conceptually, we consider an ...
  • The Tractability of Model-checking for LTL: The Good, the Bad, and the Ugly Fragments 
    Bauland, Michael; Mundhenk, Martin; Schneider, Thomas; Schnoor, Henning; Schnoor, Ilka; Vollmer, Heribert (Amsterdam : Elsevier, 2009)
    In a seminal paper from 1985, Sistla and Clarke showed that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of temporal operators used. If, in ...